Updated at 2021.5.25 Updated at 2018.10.28 같은 글이 티스토리에도 있음.

소수의 개수

소수(Prime Number)?

1과 자신의 수로만 나눠지는 수를 소수(素數)라고 하고, 영어로는 Prime Number라고 불린다. 소수가 아닌 수를 합성수라고 하는데 모든 합성수는 소수들의 곱으로 나타낼 수 있고, 이를 소인수분해(Prime Factorization)라고 한다. 다항식을 인수분해하여 단순화 시키면 그 해를 쉽게 구할 수있는 것처럼, 임의의 수의 소인수분해하는 것을 매우 중요하다.

고대 그리스 시대에서 부터 소수의 중요성은 인정되었고, 소수를 구하는 법은 에라토스테네스의 체(Sieve of Eratosthenes)라고 알려져있고, 유클리드는 소수의 개수는 무한하다고 증명하였다.

소수의 무한성 증명하기

소수의 개수가 유한하다고 가정하고 그 개수가 \(k\) 개라고 하자. 그러면 그 모든 소수의 곱으로 된 수보다 1이 큰 자연수 \(N\) 을 생각할 수 있다.

\begin{align}N = p_1 \times p_2 \times \cdots \times p_k + 1\end{align}

이 수가 새로운 소수임을 이제 추론해 보자. \(N\) 은 기존의 각 소수 \(p_i\) 로 나누면 나머지가 1이다. 따라서 1과 자신 이외의 약수가 없으로 소수이다. 이 \(N\) 은 기존의 \(k\) 개의 소수와 같지 않으므로 새로운 소수이다. 모순이다.

결론적으로 소수의 개수는 유한하지 않다.

소수의 개수는?

\(x\) 보다 작거나 같은 소수의 개수를 나타내는 함수를 일반적으로 \(\pi(x)\) 라고 하는데, 이것이 어떤 형태를 가질 것인가가 예전부터 있어 왔던 중요한 질문이었다.

\begin{align}\pi(x) = ?\end{align}

아직까지는 어떤 수식으로도 나타낼 수 없지만, 아래 그래프에 1부터 100까지의 값을 나타내었다.

더 큰 \(x\) 에 대해서도 구할 수있는데, 백억까지 나타내보면 아래 그래프와 같다. 숫자가 커서 로그 스케일로 나타내었는데, 놀랍게도 거의 직선으로 나타난다.

\begin{align}\ln \pi(x) \sim \alpha \ln x\end{align}

좀 더 자세히 보기 위해, 숫자가 크니 \(x\) 까지의 소수의 개수를 \(x\) 로 나눈 소수의 밀도를 구해보자.

\begin{align}\frac{\pi(x)}{x} = ?\end{align}

1798년에 르장드르(Legendre)가 근사적으로 아래와 같이 구했고,

\begin{align}\frac{\pi(x)}{x} = \frac{1}{\ln(x) - 1.08366}\end{align}

러시아 수학자 파프누티 체비쇼프(1821~1894)는 다음을 증명하였다고 한다.(내용 이해를 못해 자세한 것은 생략)

\begin{align}\red{\lim_{x \to \infty} \frac{\pi(x) \ln x}{x} = 1}\end{align}

위의 소수에 관한 내용은 여기를 참고했음. How many primes are there?

Most Popular #3

Recent #3